#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 5e5 + 10;

struct Node
{
    int l, r, lmax, rmax, max, sum;
}node[N * 4];

int n, m;
int q[N];

void pushup(Node& root, Node& l, Node& r){
    root.sum = l.sum + r.sum;
    root.lmax = max(l.lmax, l.sum + r.lmax);
    root.rmax = max(r.rmax, r.sum + l.rmax);
    root.max = max(max(l.max, r.max), l.rmax + r.lmax);
}

void pushup(int u){
    pushup(node[u], node[u << 1], node[u << 1 | 1]);
}

void build(int u, int l, int r){
    if(l == r){
        node[u].l = l;
        node[u].r = r;
        node[u].lmax = q[l];
        node[u].rmax = q[l];
        node[u].max = q[l];
        node[u].sum = q[l];
    }else{
        int mid = (l + r) >> 1;
        node[u].l = l, node[u].r = r;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, int p){
    if(node[u].l == x && node[u].r == x){
        node[u].lmax = p;
        node[u].rmax = p;
        node[u].max = p;
        node[u].sum = p;
    }else{
        int mid = (node[u].l + node[u].r) >> 1;
        if(x <= mid) modify(u << 1, x, p);
        else modify(u << 1 | 1, x, p);
        pushup(u);
    }
}

Node query(int u, int l, int r){
    if(node[u].l >= l && node[u].r <= r){
        return node[u];
    }else{
        int mid = (node[u].l + node[u].r) >> 1;
        if(r <= mid){
            return query(u << 1, l, r);
        }else if(l > mid){
            return query(u << 1 | 1, l, r);
        }else{
            Node temp;
            Node left = query(u << 1, l, r);
            Node right = query(u << 1 | 1, l, r);
            pushup(temp, left, right);
            return temp;
        }
    }
}

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &q[i]);

    build(1, 1, n);
    while(m --){
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if(op == 1){
            if(x > y) swap(x, y);
            Node temp = query(1, x, y);
            printf("%d\n", temp.max);
        }else{
            modify(1, x, y);
        }
    }



    return 0;
}